package leetcode;

import java.util.HashMap;
import java.util.Stack;

//最长有效括号
public class LongestValidParentheses {

	public static void main(String[] args) {
		LongestValidParentheses object = new LongestValidParentheses();
		String string = ")(()())(()))))(";
		System.out.println(object.longestValidParentheses(string));
	}
	
	//不知道是在哪看的了，反正是CSDN上面，这道题将（ 看成 -1，）看成1
	//求最长和为0的连续子串
	//当时也没细想，其实还要-1开头，比如)(())(
	//最长的应该是4，但是如果不约束-1开头的话，会得出6
	
	//还有 ())()(
	//虽然是以-1开头的，但是中间不满足
    public int longestValidParentheses(String s) {
        if(s == null || s.length() <= 0){
        	return 0;
        }
        int length = s.length();
        int[] nums = new int[length];
        for(int i = 0; i < length; i++){
        	if(s.charAt(i) == '('){
        		nums[i] = -1;
        	}else{
        		nums[i] = 1;
        	}
        }
        //接下来求最长连续和为0的子数组
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0,  -1);
        int curSum = 0;
        int maxLength = 0;
        for(int i = 0; i < length; i++){
        	curSum += nums[i];
        	Integer index;
        	if( (index = map.get(curSum)) != null){
        		if(nums[index + 1] == -1){
        			maxLength = Math.max(maxLength, i - index);
        		}
        	}else{
        		map.put(curSum, i);
        	}
        }
        return maxLength;
    }
    
    //solution2
    public int longestValidParentheses_2(String s) {
    	if(s == null || s.length() <= 0){
        	return 0;
        }
        int length = s.length();
    	Stack<Integer> left = new Stack<>();
    	Stack<Integer> right = new Stack<>();
    	int maxLength = 0;
    	int lastRight = -1, lastLeft = -1;
    	int curLength = 0;
    	for(int i = 0; i < length; i++){
    		if(s.charAt(i) == '('){
    			left.push(i);
    		}else{
    			if(!left.isEmpty()){
    				int curLeftIndex = left.pop();
    				if(lastRight == -1 || curLeftIndex == lastRight + 1 || curLeftIndex == lastLeft - 1){
    					curLength += 2;
    				}else{
    					//同样是这里的问题，不知道怎么更新啊
    					curLength = 2;
    				}
    				lastRight = i;
    				lastLeft = curLeftIndex;
    				maxLength = Math.max(curLength, maxLength);
    			}
    			curLength = 0;
    			
//    			if(left.size() == right.size()){
//    				maxLength = Math.max(left.size() * 2, maxLength);
//    				left.clear();
//    				right.clear();
//    			}else{
//    				right.push(i);
//    			}
    		}
    	}
    	//最后获取maxLength的时候也不知道该怎样获取比如 ((( )) ((())(())
    	//可能存在很多种 ( 比 ) 多的可能
    	maxLength = Math.max(right.size() * 2, maxLength);
    	return maxLength;
    }
    
    //others' code
    //思想是找到所有不匹配的下标，这些下标将s分成了很多段，我们可以统计这些段的最大长度
    //超时了...
    public int longestValidParentheses_3(String s) {
		if (s == null || s.length() <= 0) {
			return 0;
		}
		int length = s.length();
		Stack<Integer> stack = new Stack<>();
		for (int i = 0; i < length; i++) {
			if (s.charAt(i) == '(') {
				stack.push(i);
			} else {
				if (!stack.empty()) {
					if (s.charAt(stack.peek()) == '(') {
						stack.pop();
					} else {
						stack.push(i);
					}
				} else {
					stack.push(i);
				}
			}
		}
		//如果此时栈为空，说明整段字符串都是满足的，直接返回即可
    	if(stack.isEmpty()){
    		return length;
    	}
    	int res = 0;
    	int a = length, b = 0;
        while (!stack.empty()) {
            b = stack.pop();
            //本来应该是是length - 1 - (b + 1) + 1
            //为了后面的统一，我们将a初始化成length
            res = Math.max(res, a - b - 1);
            //如果初始化为length - 1, a = b - 1;
            a = b;
        }
        //还要计算最后的一段
        res = Math.max(res, a);
        return res;
    }
    
    //runtime is better. but still TLE
	public int longestValidParentheses_3_2(String s) {
		int max = Integer.MIN_VALUE;
		s += "x";
		Stack<Integer> stack = new Stack<>();
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == ')' && !stack.empty()
					&& s.charAt(stack.peek()) == '(')
				stack.pop();
			else {
				if (stack.empty()) {
					max = Math.max(max, i);
				} else
					max = Math.max(max, i - stack.peek() - 1);
				stack.push(i);
			}
		}
		return stack.empty() ? s.length() : max;
	}
    
    //dp solution 
    
    public int longestValidParentheses_4(String s) {
        int[] dp = new int[s.length() + 1];
        char[] array = s.toCharArray();
        int max = 0;
        for(int i = 2, j = 0; i < dp.length; i++){
            if(array[i - 1] == ')'){
                if(array[i - 2] == '('){
                    dp[i] = dp[i - 2] + 2;
                }else if((j = i - dp[i - 1] - 1) >= 1 && array[j - 1] == '('){
                    dp[i] = dp[j - 1] + dp[i - 1] + 2;
                }
                max = Math.max(max, dp[i]);
            }
        }
        return max;
    }
    
    //other dp slution
    public int longestValidParentheses_5(String s) {
        char[] S = s.toCharArray();
        
        //V[i]表示0...i的最长匹配长度
        int[] V = new int[S.length];
        int open = 0;
        int max = 0;
        for (int i=0; i<S.length; i++) {
            if (S[i] == '(') open++;
            if (S[i] == ')' && open > 0) {
                // matches found
                V[i] = 2 + V[i-1];
                // add matches of previous
                //可以看到跟我之前匹配栈的想法很像
                //i - V[i]是当前匹配的长度的前一个字符
                if(i - V[i] > 0)
                    V[i] += V[i - V[i]];
                open--;
            }
            if (V[i] > max) max = V[i];
        }
        return max;
    }
}
